Regular Grammar
   HOME

TheInfoList



OR:

In
theoretical computer science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...
and
formal language theory In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of symb ...
, a regular grammar is a
grammar In linguistics, the grammar of a natural language is its set of structure, structural constraints on speakers' or writers' composition of clause (linguistics), clauses, phrases, and words. The term can also refer to the study of such constraint ...
that is ''right-regular'' or ''left-regular''. While their exact definition varies from textbook to textbook, they all require that * all production rules have at most one
non-terminal symbol In computer science, terminal and nonterminal symbols are the lexical elements used in specifying the production rules constituting a formal grammar. ''Terminal symbols'' are the elementary symbols of the language defined by a formal grammar. ...
; * that symbol is either always at the end or always at the start of the rule's right-hand side. Every regular grammar describes a
regular language In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
.


Strictly regular grammars

A right-regular grammar (also called right-linear grammar) is a formal grammar (''N'', Σ, ''P'', ''S'') in which all production rules in ''P'' are of one of the following forms: # ''A'' → ''a'' # ''A'' → ''aB'' # ''A'' → ε where ''A'', ''B'', ''S'' ∈ ''N'' are non-terminal symbols, ''a'' ∈ Σ is a terminal symbol, and ε denotes the
empty string In formal language theory, the empty string, or empty word, is the unique string of length zero. Formal theory Formally, a string is a finite, ordered sequence of characters such as letters, digits or spaces. The empty string is the special cas ...
, i.e. the string of length 0. ''S'' is called the start symbol. In a left-regular grammar, (also called left-linear grammar), all rules obey the forms # ''A'' → ''a'' # ''A'' → ''Ba'' # ''A'' → ε The language described by a given grammar is the set of all strings that contain only terminal symbols and can be derived from the start symbol by repeated application of production rules. Rules of both kinds must not be mixed; for example, the grammar with rule set is not regular, and describes the language , which is not regular, either. Some textbooks and articles disallow empty production rules, and assume that the empty string is not present in languages.


Extended regular grammars

An ''extended right-regular grammar'' is one in which all rules obey one of # ''A'' → ''w'', where ''A'' is a non-terminal in ''N'' and ''w'' is in a (possibly empty) string of terminals Σ* # ''A'' → ''wB'', where ''A'' and ''B'' are in ''N'' and ''w'' is in Σ*. Some authors call this type of grammar a ''right-regular grammar'' (or ''right-linear grammar'') and the type above a ''strictly right-regular grammar'' (or ''strictly right-linear grammar''). An ''extended left-regular grammar'' is one in which all rules obey one of # ''A'' → ''w'', where ''A'' is a non-terminal in ''N'' and ''w'' is in Σ* # ''A'' → ''Bw'', where ''A'' and ''B'' are in ''N'' and ''w'' is in Σ*.


Examples

An example of a right-regular grammar ''G'' with ''N'' = , Σ = , ''P'' consists of the following rules : S → aS : S → bA : A → ε : A → cA and S is the start symbol. This grammar describes the same language as the
regular expression A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" ...
a*bc*, viz. the set of all strings consisting of arbitrarily many "''a''"s, followed by a single "''b''", followed by arbitrarily many "''c''"s. A somewhat longer but more explicit extended right-regular grammar ''G'' for the same regular expression is given by ''N'' = , Σ = , where ''P'' consists of the following rules: : S → A : A → aA : A → B : B → bC : C → ε : C → cC ...where each uppercase letter corresponds to phrases starting at the next position in the regular expression. As an example from the area of programming languages, the set of all strings denoting a floating point number can be described by an extended right-regular grammar ''G'' with ''N'' = , Σ = , where S is the start symbol, and ''P'' consists of the following rules: :


Expressive power

There is a direct one-to-one correspondence between the rules of a (strictly) right-regular grammar and those of a
nondeterministic finite automaton In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if * each of its transitions is ''uniquely'' determined by its source state and input symbol, and * reading an input symbol is required for each state ...
, such that the grammar generates exactly the language the automaton accepts. Hence, the right-regular grammars generate exactly all
regular language In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
s. The left-regular grammars describe the reverses of all such languages, that is, exactly the regular languages as well. Every strict right-regular grammar is extended right-regular, while every extended right-regular grammar can be made strict by inserting new non-terminals, such that the result generates the same language; hence, extended right-regular grammars generate the regular languages as well. Analogously, so do the extended left-regular grammars. If empty productions are disallowed, only all regular languages that do not include the empty string can be generated.Hopcroft and Ullman 1979, p.229, Exercise 9.2 While regular grammars can only describe regular languages, the converse is not true: regular languages can also be described by non-regular grammars.


Mixing left-regular and right-regular rules

If mixing of left-regular and right-regular rules is allowed, we still have a
linear grammar In computer science, a linear grammar is a context-free grammar that has at most one nonterminal in the right-hand side of each of its productions. A linear language is a language generated by some linear grammar. Example An example of a linear gr ...
, but not necessarily a regular one. What is more, such a grammar need not generate a regular language: all linear grammars can be easily brought into this form, and hence, such grammars can generate exactly all linear languages, including non-regular ones. For instance, the grammar ''G'' with ''N'' = , Σ = , ''P'' with start symbol ''S'' and rules : S → aA : A → Sb : S → ε generates \, the paradigmatic non-regular linear language.


See also

*
Regular expression A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" ...
, a compact notation for regular grammars *
Regular tree grammar In theoretical computer science and formal language theory, a regular tree grammar is a formal grammar that describes a set of directed trees, or terms. A regular word grammar can be seen as a special kind of regular tree grammar, describing a se ...
, a generalization from strings to trees *
Prefix grammar A prefix is an affix which is placed before the stem of a word. Adding it to the beginning of one word changes it into another word. For example, when the prefix ''un-'' is added to the word ''happy'', it creates the word ''unhappy''. Particula ...
*
Chomsky hierarchy In formal language theory, computer science and linguistics, the Chomsky hierarchy (also referred to as the Chomsky–Schützenberger hierarchy) is a containment hierarchy of classes of formal grammars. This hierarchy of grammars was described by ...
* * , chapter III


References

{{DEFAULTSORT:Regular Grammar Formal languages